package com.kitty.record.kittyalgorithm.basicalgorithm;

/**
 * 二分查找算法
 *二分查找又叫折半查找，要求带查找的序列有序。每次取中间位置的值与待查找的关键字作比较，
 * 如果中间位置的值比关键字大，则在前半部分循环这个过程；如果中间位置的值比关键字小，则在
 * 后半部分循环这个过程；知道找到为止，否则序列中就没有这个关键字对应的值。
 *
 *
 *
 * @Author SHEN
 * @Date 2020/12/28
 */
public class BinarySearch {

    public static void main(String[] args) {

        int[] arr = new int[]{1,4,5,6,8,9};
        //System.out.println("binarySearch(arr,4) = " + binarySearch(arr, 4));

        System.out.println("bSearchForRecursion(arr,6) = " + bSearchForRecursion(arr, 6));


    }

    //循环的方式实现二分查找
    public static int binarySearch(int[] array, int keyWorld){
        int lo = 0;

        int hi = array.length;

        int mid;

        while (lo <= hi){

            mid = (lo+hi)/2;

            if(keyWorld == array[mid]){
                return mid;
            }

            if(keyWorld < array[mid]){
                hi = mid;
            }


            if(keyWorld > array[mid]){
                lo = mid;
            }

        }
        return -1;
    }



    //递归的方式实现二分查找
    public static int bSearchForRecursion(int[] array ,int key){

        int lo = 0;

        int hi = array.length;

        return bSearch(array,key,lo,hi);
    }

    public static int bSearch(int[] array ,int key,int lo,int hi){

        int mid = (lo+hi)/2;

        if(key == array[mid]){
            return mid;
        }

        if(key < array[mid]){
            return bSearch(array,key,lo,mid);
        }

        if(key > array[mid]){
            return bSearch(array,key,mid,hi);
        }
        return -1;
    }


}
